package datastructure.book.dp._1_pathway.all;

public class _3_Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] cntArr = new int[m][n];
        cntArr[0][0] = grid[0][0];
        cntArr[m-1][n-1] = grid[m-1][n-1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    if (cntArr[i - 1][j] < cntArr[i][j - 1]) {
                        cntArr[i][j] = cntArr[i - 1][j] + grid[i][j];
                    } else {
                        cntArr[i][j] = cntArr[i][j - 1] + grid[i][j];
                    }
                } else if (i > 0) {
                    cntArr[i][j] = cntArr[i - 1][j] + grid[i][j];
                } else if (j > 0) {
                    cntArr[i][j] = cntArr[i][j - 1] + grid[i][j];
                }
            }
        }
        return cntArr[m-1][n-1];
    }
}
